class Solution {
    class SegTree
    {
        public:
        int start,end,status;
        SegTree* left;
        SegTree* right;
        SegTree(int a, int b, int s):start(a),end(b),status(s),left(NULL),right(NULL){}
        
        void remove(SegTree* &node)
        {
            if (node==NULL) return;
            remove(node->left);
            remove(node->right);
            delete node;
            node = NULL;
            return;            
        }
        
        void setStatus(int a, int b, int s)
        {
            if (a>=end || b<=start)
                return;
            if (a<=start && b>=end && s>=status)
            {
                remove(left);
                remove(right);
                status = s;
                return;
            }
            if (a<=start && b>=end && s<status && left==NULL)
                return;
            if (left==NULL)
            {
                int mid = start+(end-start)/2;
                left = new SegTree(start,mid,status);
                right = new SegTree(mid,end,status);
            }
            left->setStatus(a,b,s);
            right->setStatus(a,b,s);
            status = max(left->status,right->status);            
        }
    };
public:
    vector<pair<int,int>>results;
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) 
    {
        if (buildings.size()==0) return {};
        
        SegTree* root = new SegTree(0,INT_MAX,0);
        for (auto q:buildings)
            root->setStatus(q[0],q[1],q[2]);
        
        DFS(root);
        if (results.back().second!=0) results.push_back({INT_MAX,0});
        
        vector<pair<int,int>>filteredResults;
        for (auto p: results)
        {
            if (filteredResults.size()!=0 && p.second==filteredResults.back().second)
                continue;
            filteredResults.push_back({p.first,p.second});
        }
        if (filteredResults.size()!=0 && filteredResults[0].second==0) filteredResults.erase(filteredResults.begin());
        return filteredResults;
    }
    
    void DFS(SegTree* node)
    {        
        if (node->left==NULL)
            results.push_back({node->start,node->status});
        else
        {
            DFS(node->left);
            DFS(node->right);
        }
    }
};
